package org.example.SolutionNew005;

import java.util.*;

public class Backtrack007 {
    public static void main(String[] args) {
        Backtrack007 b=new Backtrack007();
        System.out.println(b.solveNQueens(1).toString());

    }

    //列和两种斜线都有其规律
    public List<List<String>> solveNQueens1(int n) {
        List<List<String>> res=new ArrayList<>();
        int[] queue=new int[n];
        Set<Integer> col=new HashSet<>();
        Set<Integer> diagonals1=new HashSet<>();
        Set<Integer> diagonals2=new HashSet<>();
        findTheList(res,queue,n,0,col,diagonals1,diagonals2);
        return res;
    }

    private void findTheList(List<List<String>> res, int[] queue, int n, int i, Set<Integer> col, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (i == n) {
            List<String> list = getAnswer(queue, n);
            res.add(list);
        } else {
            for (int j = 0; j < n; j++) {
                if (col.contains(j)) continue;
                int diagonal1 = i - j;
                if (diagonals1.contains(diagonal1)) continue;
                int diagonal2 = i + j;
                if (diagonals2.contains(diagonal2)) continue;
                queue[i] = j;
                col.add(j);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                findTheList(res, queue, n, i + 1, col, diagonals1, diagonals2);
                col.remove(j);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

        public List<String> getAnswer(int[] queue,int n) {
            List<String> list=new ArrayList<>();
            for(int i=0;i<n;i++){
                char[] tmp=new char[n];
                Arrays.fill(tmp,'.');
                tmp[queue[i]]='Q';
                String que=new String(tmp);
                list.add(que);
            }
            return list;
        }


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res=new ArrayList<>();
        int[] queue=new int[n];
        Arrays.fill(queue, -1);
        solve(res,queue,n,0,0,0,0);
        return res;
    }

    private void solve(List<List<String>> res, int[] queue, int n, int i, int col, int dia1, int dia2) {
        if(i==n){
            List<String> list=getAnswer(queue,n);
            res.add(list);
        }else{
            int canBeUsedPosition=((1<<n)-1) & (~(col | dia1 |dia2));
            while(canBeUsedPosition!=0){
                int position=canBeUsedPosition & (-canBeUsedPosition);
                canBeUsedPosition=canBeUsedPosition& (canBeUsedPosition-1);
                int column=Integer.bitCount(position-1);
                queue[i]=column;
                solve(res,queue,n,i+1,col | position,(dia1| position)<<1,(dia2| position)>>1);
                queue[i]=-1;
            }
        }
    }
}
